class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        n=N
        k=K
        direction=1
        while n>2:
            if k>2**(n-2):
               k=k-2**(n-2)
               direction=direction*-1
            n-=1
        if k==1:
            if direction==1:
                return 0
            else:
                return 1
        if k==2:
            if direction==1:
                return 1
            else:
                return 0